import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-08
 * Time: 21:38
 */
//判断一棵树是不是完全二叉树
public class Exercise1 {
    static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public int val;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();

            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }

        while(!queue.isEmpty()) {
            TreeNode peek = queue.peek();
            //这里的null是一个元素不是，空的意思
            if(peek != null) {
                return false;
            }

            //可以全部弹完，说明队列都是 null 元素.就是完全二叉树
            queue.poll();
        }
        return true;
    }
}
